#include <stdio.h>
#include <malloc.h>

#define MAX_SIZE 100

typedef struct
{
    char data[MAX_SIZE]; // 串中字符
    int length; // 串长
}SqString; // 声明顺序串类型

/*-----------------将字符串常量赋给串s--------------------*/
static void str_assign(SqString &s, char cstr[])
{
    int i;

    for(i = 0; cstr[i] != '\0'; i++)
        s.data[i] = cstr[i];
    s.length = i;
}

/*-----------------销毁串--------------------*/
static void destroy_str(SqString &s)
{

}

/*-----------------输出串s--------------------*/
static void disp_str(SqString s)
{
    int i;

    if(s.length > 0)
    {
        for(i = 0; i < s.length; i++)
            printf("%c", s.data[i]);
        printf("\n");
    }
}
static SqString *max_sub_str(SqString s)
{
    SqString *subs;
    int index = 0; // 最长重复子串的下标
    int length = 0; // 最长重复子串的长度
    int i = 0, j, k;
    int length1;

    while(i < s.length)
    {
        j = i + 1;
        while(j < s.length)
        {
            if(s.data[i] == s.data[j]) // 找一子串,其序号为i,长度为length1
            {
                length1 = 1;
                for(k = 1; s.data[i + k] == s.data[j + k]; k++)
                    length1++;
                if(length1 > length) // 将较大长度者赋给index与length
                {
                    index = i;
                    length = length1;
                }
                j += length1;
            }
            else
                j++;
        }
        i++; // 继续扫描第i字符之后的字符
    }

    subs = (SqString *)malloc(sizeof(SqString));
    subs->length = length;
    for(i = 0; i < length; i++) // 将最长重复子串复制到subs中
        subs->data[i] = s.data[index + i];

    return subs;
}

int main(int argc, char *argv[])
{
    char str[MAX_SIZE];
    SqString s, *subs;

    printf("输入串:");
    gets(str);
    str_assign(s, str); // 创建串s
    subs = max_sub_str(s);
    printf("求最长重复子串:\n");
    printf("    原串:");
    disp_str(s);
    printf("  最长重复子串:"); // 输出最长重复子串
    disp_str(*subs);
    destroy_str(s);
    free(subs);

    return 0;
}
